/*
;; MIT License

;; Copyright (c) 2025 三体自动化技术协会

;; Permission is hereby granted, free of charge, to any person obtaining a copy
;; of this software and associated documentation files (the "Software"), to deal
;; in the Software without restriction, including without limitation the rights
;; to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
;; copies of the Software, and to permit persons to whom the Software is
;; furnished to do so, subject to the following conditions:

;; The above copyright notice and this permission notice shall be included in all
;; copies or substantial portions of the Software.

;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
;; IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
;; FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
;; AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
;; LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
;; OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
;; SOFTWARE.
*/

#include<stdint.h>

// 希尔伯特曲线：从节点序号到坐标的映射
// n: 曲线阶数 (网格大小 = 2^n × 2^n)
// d: 节点序号 (0 到 2^(2n)-1)
// x, y: 输出的坐标 (0 到 2^n-1)
void hilbert_d2xy(int n, uint32_t d, uint32_t *x, uint32_t *y) {
    uint32_t rx, ry, s;
    uint32_t t = d;

    *x = *y = 0;

    for (s = 1; s < (1U << n); s *= 2) {
        rx = (t / 2) & 1;
        ry = (t ^ rx) & 1;

        // 旋转和翻转
        if (ry == 0) {
            if (rx == 1) {
                *x = s - 1 - *x;
                *y = s - 1 - *y;
            }
            // 交换 x 和 y
            uint32_t temp = *x;
            *x = *y;
            *y = temp;
        }

        *x += s * rx;
        *y += s * ry;

        t /= 4;
    }
}

// 希尔伯特曲线：从坐标到节点序号的映射
// n: 曲线阶数
// x, y: 输入坐标 (0 到 2^n-1)
// 返回值: 节点序号 (0 到 2^(2n)-1)
uint32_t hilbert_xy2d(int n, uint32_t x, uint32_t y) {
    uint32_t rx, ry, s, d = 0;

    for (s = (1U << (n - 1)); s > 0; s /= 2) {
        rx = (x & s) ? 1 : 0;
        ry = (y & s) ? 1 : 0;

        d += s * s * ((3 * rx) ^ ry);

        // 旋转坐标
        if (ry == 0) {
            if (rx == 1) {
                x = s - 1 - x;
                y = s - 1 - y;
            }
            // 交换 x 和 y
            uint32_t temp = x;
            x = y;
            y = temp;
        }
    }
    return d;
}


enum Direction { RIGHT, UP, LEFT, DOWN };

char *arr1[][4] ={
	{ "═", "╝", "═", "╗", },
	{ "╔", "║", "╗", "║", },
	{ "═", "╚", "═", "╔", },
	{ "╚", "║", "╝", "║", },
};

enum Direction get_direction(uint32_t x1, uint32_t y1, uint32_t x2, uint32_t y2) {
    if (x2 > x1) return RIGHT;
    if (x2 < x1) return LEFT;
    if (y2 > y1) return UP;
    return DOWN;
}

#include<stdlib.h>
#include<stdio.h>
int main(int argc, char *argv[]) {
    int n = 3; // 默认值

    // 从命令行参数读取n
    if (argc > 1) {
        n = atoi(argv[1]);
        if (n <= 0) {
            printf("参数错误！使用默认值 n=3\n");
            n = 3;
        }
    }

    uint32_t size = 1U << n;  // 2^n
    uint32_t total_points = size * size;

    // 存储所有点的坐标
    uint32_t *coords_x = malloc(total_points * sizeof(uint32_t));
    uint32_t *coords_y = malloc(total_points * sizeof(uint32_t));

    if (!coords_x || !coords_y) {
        printf("内存分配失败！\n");
        free(coords_x);
        free(coords_y);
        return 1;
    }

    // 计算所有点的坐标
    for (uint32_t d = 0; d < total_points; d++) {
        hilbert_d2xy(n, d, &coords_x[d], &coords_y[d]);
    }

    // 创建网格用于存储字符
    char ***grid = malloc(size * sizeof(char**));
    for (uint32_t i = 0; i < size; i++) {
        grid[i] = malloc(size * sizeof(char*));
        for (uint32_t j = 0; j < size; j++) {
            grid[i][j] = " ";
        }
    }

    // 填充网格
    for (uint32_t d = 0; d < total_points; d++) {
        uint32_t x = coords_x[d];
        uint32_t y = coords_y[d];

        if (d < total_points - 1) {
            uint32_t next_x = coords_x[d + 1];
            uint32_t next_y = coords_y[d + 1];

            enum Direction from_dir, to_dir;

            // 确定方向
            if (d == 0) {
                // 第一个点，只有去向
                to_dir = get_direction(x, y, next_x, next_y);
                from_dir = to_dir;  // 假设进入方向与离开方向相同
            } else {
                uint32_t prev_x = coords_x[d - 1];
                uint32_t prev_y = coords_y[d - 1];
                from_dir = get_direction(prev_x, prev_y, x, y);
                to_dir = get_direction(x, y, next_x, next_y);
            }

            grid[y][x] = arr1[from_dir][to_dir];
        } else {
            // 最后一个点，只有进入方向
            uint32_t prev_x = coords_x[d - 1];
            uint32_t prev_y = coords_y[d - 1];
            enum Direction from_dir = get_direction(prev_x, prev_y, x, y);
            grid[y][x] = arr1[from_dir][from_dir];  // 使用相同方向
        }
    }

    // 打印希尔伯特曲线
    // printf("\n希尔伯特曲线 (n=%d):\n", n);

    // 注意：由于终端通常y轴向下，我们需要翻转y坐标来正确显示
    for (int y = size - 1; y >= 0; y--) {
        for (uint32_t x = 0; x < size; x++) {
            printf("%s", grid[y][x]);
        }
        printf("\n");
    }

    // 清理内存
    for (uint32_t i = 0; i < size; i++) {
        free(grid[i]);
    }
    free(grid);
    free(coords_x);
    free(coords_y);

    return 0;
}
